//
//  ExamGraph.m
//  ocdemo
//
//  Created by JIENING ZHANG on 2020/5/10.
//  Copyright © 2020 JIENING ZHANG. All rights reserved.
//

#import "ExamGraph.h"


@interface TNode : NSObject

// 前置节点数组，存放前置节点对象
@property (nonatomic, strong) NSMutableArray<TNode*> *preNodeList;

@property (nonatomic, copy) NSString *nodeName;

// 添加前置节点
-(void) addPreNode:(TNode *)preNode;

-(BOOL)checkLoop:(NSArray<TNode*> *)nodePathFromEnd;
@end

@implementation TNode

- (instancetype)init {
    if (self = [super init]) {
        _preNodeList = [NSMutableArray array];
    }
    return self;
}

// 添加前置节点
-(void) addPreNode:(TNode *)preNode {
    if(preNode==nil || preNode == self) {
        return;
    }

    @synchronized (_preNodeList) {
        // 遍历查看是否已经存在，如果已经存在就不添加节点了
        if([_preNodeList containsObject:preNode]) {
            return;
        }
        // 不存在，添加节点
        [_preNodeList addObject:preNode];
    }
}

-(BOOL)checkLoop:(NSArray<TNode*> *)nodePathFromEnd {
    if([nodePathFromEnd containsObject:self]) {
        NSLog(@"in checkLoop, found loop, print nodePathFromEnd");
        for(TNode *node in nodePathFromEnd){
            NSLog(@" %@", node.nodeName);
        }
        NSLog(@" %@", self.nodeName);
        return YES;
    }
    
    for(TNode *pre in _preNodeList){
        // 构建新的 节点路径，将self节点加入进去，向下递归
        NSMutableArray *nodePath = [NSMutableArray arrayWithArray:nodePathFromEnd];
        [nodePath addObject:self];
        
        if([pre checkLoop:nodePath]) {
            return YES;
        }
    }
    
    return NO;
}

@end


// 由TNode组成的有向图
@interface TGraph : NSObject

// 向有向图添加n个节点，并且设置前后关联关系 pNodes[0] --(isStrong)--> pNodes[1] --(isStrong)--> pNodes[2] ...  --(isStrong)--> pNodes[n-1]
-(void) addNodeSequeceIntoGraph:(NSArray<TNode *> *)pNodes;

// 向有向图 添加preNode节点 和 subNodeList中所有节点，并且如下设置前后关联关系
//  preNode --> subNode[0]
//  preNode --> subNode[1]
//  ...
//  preNode --> subNode[n-1]
-(void) addNodeIntoGraph:(TNode *)preNode subNodeList:(NSArray<TNode *> *)subNodeList;

// 向有向图 添加preNode节点 和 subNodeList中所有节点，并且如下设置前后关联关系
//  preNode[0] --> subNode
//  preNode[1] --> subNode
//  ...
//  preNode[n-1] --> subNode
-(void) addNodesIntoGraph:(NSArray<TNode *> *)preNode subNode:(TNode *)subNode;

// 检测 由TNode组成的有向图 是否存在环
-(BOOL)checkLoopInGraphWithStart:(TNode*)startNode andEnd:(TNode*)endNode;

@property (nonatomic, strong) NSMutableArray<TNode*> *nodes;
@end

@implementation TGraph

- (instancetype)init {
    if (self = [super init]) {
        _nodes = [NSMutableArray array];
    }
    return self;
}

// 向有向图添加n个节点，并且设置前后关联关系 pNodes[0] --(isStrong)--> pNodes[1] --(isStrong)--> pNodes[2] ...  --(isStrong)--> pNodes[n-1]
-(void) addNodeSequeceIntoGraph:(NSArray<TNode *> *)pNodes {
    //todo
    @synchronized (self) {
        TNode *preNode=nil;
        for(TNode *node in pNodes) {
            if(! [_nodes containsObject:node]) {
                [_nodes addObject:node];
            }
            
            if(preNode) {
                [node addPreNode:preNode];
            }
            
            preNode = node;
        }
    }
}

// 向有向图 添加preNode节点 和 subNodeList中所有节点，并且如下设置前后关联关系
//  preNode --> subNode[0]
//  preNode --> subNode[1]
//  ...
//  preNode --> subNode[n-1]
-(void) addNodeIntoGraph:(TNode *)preNode subNodeList:(NSArray<TNode *> *)subNodeList {
    //todo
    
    if(!preNode) {
        return;
    }
    
    @synchronized (self) {
        if(! [_nodes containsObject:preNode]) {
            [_nodes addObject:preNode];
        }
        
        for(TNode *node in subNodeList) {
            if(! [_nodes containsObject:node]) {
                [_nodes addObject:node];
            }
            
            [node addPreNode:preNode];
        }
    }
}

// 向有向图 添加preNode节点 和 subNodeList中所有节点，并且如下设置前后关联关系
//  preNode[0] --> subNode
//  preNode[1] --> subNode
//  ...
//  preNode[n-1] --> subNode
-(void) addNodesIntoGraph:(NSArray<TNode *> *)preNodes subNode:(TNode *)subNode {
    //todo
    
    if(!subNode) {
        return;
    }
    
    @synchronized (self) {
        if(! [_nodes containsObject:subNode]) {
            [_nodes addObject:subNode];
        }
        
        for(TNode *node in preNodes) {
            if(! [_nodes containsObject:node]) {
                [_nodes addObject:node];
            }
            
            [subNode addPreNode:node];
        }
    }
}


// 检测 由TNode组成的有向图 是否存在环
-(BOOL)checkLoopInGraphWithStart:(TNode*)startNode andEnd:(TNode*)endNode {
    // todo
    if(! endNode) {
        return NO;
    }
    
    for(TNode* pre in endNode.preNodeList) {
        if([pre checkLoop:@[endNode]]){
            return YES;
        }
    }
    
    return NO;
}
@end


@implementation ExamGraph

+ (void)testLogic1 {
    TNode *node0 = [TNode new]; node0.nodeName = @"n0";
    TNode *node1 = [TNode new]; node1.nodeName = @"n1";
    TNode *node2 = [TNode new]; node2.nodeName = @"n2";
    TNode *node3 = [TNode new]; node3.nodeName = @"n3";
    
    TNode *nodeA = [TNode new]; nodeA.nodeName = @"nA";
    TNode *nodeB = [TNode new]; nodeB.nodeName = @"nB";
    TNode *nodeC = [TNode new]; nodeC.nodeName = @"nC";
    TNode *nodeD = [TNode new]; nodeD.nodeName = @"nD";
    TNode *nodeE = [TNode new]; nodeE.nodeName = @"nE";
    TNode *nodeF = [TNode new]; nodeF.nodeName = @"nF";
    
    TGraph *testGraph = [TGraph new];
    
    //*
    //串行 node1 --> node2 --> nodeA --> nodeB --> nodeC --> nodeD --> nodeE --> nodeF（end）
    [testGraph addNodeSequeceIntoGraph:@[node1, node2, node3, nodeA, nodeB, nodeC, nodeD, nodeE, nodeF]];
    //*/
    
    if([testGraph checkLoopInGraphWithStart:node1 andEnd:nodeF]) {
        //
        NSLog(@"testLogic1, loop found");
    } else {
        //
        NSLog(@"testLogic1, loop not found");
    }
}

+ (void)testLogic2 {
    TNode *node0 = [TNode new]; node0.nodeName = @"n0";
    TNode *node1 = [TNode new]; node1.nodeName = @"n1";
    TNode *node2 = [TNode new]; node2.nodeName = @"n2";
    TNode *node3 = [TNode new]; node3.nodeName = @"n3";
    
    TNode *nodeA = [TNode new]; nodeA.nodeName = @"nA";
    TNode *nodeB = [TNode new]; nodeB.nodeName = @"nB";
    TNode *nodeC = [TNode new]; nodeC.nodeName = @"nC";
    TNode *nodeD = [TNode new]; nodeD.nodeName = @"nD";
    TNode *nodeE = [TNode new]; nodeE.nodeName = @"nE";
    TNode *nodeF = [TNode new]; nodeF.nodeName = @"nF";
    
    TGraph *testGraph = [TGraph new];
    
    //* 并行  node1 -->  node0 --------> nodeF（end）
    //              ↘   node2 ________↗
    //              ↘   nodeA ________↗
    //              ↘   nodeB ________↗
    //              ↘   nodeC ________↗
    //              ↘   nodeD ________↗
    //              ↘   nodeE ________↗
    [testGraph addNodeIntoGraph:node1 subNodeList:@[node0, node2, node3, nodeA, nodeB, nodeC, nodeD, nodeE]];
    [testGraph addNodesIntoGraph:@[node0, node2, node3, nodeA, nodeB, nodeC, nodeD, nodeE] subNode:nodeF];
    //*/
    
    if([testGraph checkLoopInGraphWithStart:node1 andEnd:nodeF]) {
        //
        NSLog(@"testLogic2, loop found");
    } else {
        //
        NSLog(@"testLogic2, loop not found");
    }
}

+ (void)testLogic3 {
    TNode *node0 = [TNode new]; node0.nodeName = @"n0";
    TNode *node1 = [TNode new]; node1.nodeName = @"n1";
    TNode *node2 = [TNode new]; node2.nodeName = @"n2";
    TNode *node3 = [TNode new]; node3.nodeName = @"n3";
    
    TNode *nodeA = [TNode new]; nodeA.nodeName = @"nA";
    TNode *nodeB = [TNode new]; nodeB.nodeName = @"nB";
    TNode *nodeC = [TNode new]; nodeC.nodeName = @"nC";
    TNode *nodeD = [TNode new]; nodeD.nodeName = @"nD";
    TNode *nodeE = [TNode new]; nodeE.nodeName = @"nE";
    TNode *nodeF = [TNode new]; nodeF.nodeName = @"nF";
    
    TGraph *testGraph = [TGraph new];
    
    //*有环
    //     node1 --> node2 -->  nodeC -->   nodeE --> nodeF（end）
    //           --↘  nodeA -->  nodeD _____↗  |
    //           --↘  nodeB _____↗             |
    //                  ↑                      |
    //                  ↑______________________|
    [testGraph addNodeSequeceIntoGraph:@[node1, node2, nodeC, nodeE, nodeF]];
    [testGraph addNodeSequeceIntoGraph:@[node1, nodeA, nodeD, nodeE]];
    [testGraph addNodeSequeceIntoGraph:@[node1, nodeB, nodeD]];
    [testGraph addNodeSequeceIntoGraph:@[nodeE, nodeB]];
    //*/
    
    if([testGraph checkLoopInGraphWithStart:node1 andEnd:nodeF]) {
        //
        NSLog(@"testLogic3, loop found");
    } else {
        //
        NSLog(@"testLogic3, loop not found");
    }
}

+ (void)demoLogic {
    [ExamGraph testLogic1];
    [ExamGraph testLogic2];
    [ExamGraph testLogic3];
}

// 串行  node1 --> node2 --> nodeA --> nodeB --> nodeC --> nodeD --> nodeE --> nodeF（end）


// 并行  node1 -->   node0 --------> nodeF（end）
//              ↘   node2 ________↗
//              ↘   nodeA ________↗
//              ↘   nodeB ________↗
//              ↘   nodeC ________↗
//              ↘   nodeD ________↗
//              ↘   nodeE ________↗


//串并行 node1 --> node2 -->  nodeC -->  nodeE --> nodeF（end）
//              ↘ nodeA -->  nodeD _______↗
//              ↘ nodeB __________________↗
 

// 有环 node1 -->  node2 -->  nodeC -->   nodeE --> nodeF（end）
//           --↘  nodeA -->  nodeD _____↗  |
//           --↘  nodeB _____↗             |
//                  ↑                      |
//                  ↑______________________|

@end
